package array.MinimumSizeSubarray;

/**
 * 题目: 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
        示例：
         输入：s = 7, nums = [2,3,1,2,4,3]
         输出：2
         解释：子数组 [4,3] 是该条件下的长度最小的子数组。

 * 思路:①暴力法，②滑动窗口
 */

/**
 * 暴力法:
 * //i是区间的起始位置，j是区间的终止位置
 * class Solution {
 *     public int minSubArrayLen(int target, int[] nums) {
 *         int result=Integer.MAX_VALUE;//最终返回的结果
 *         int subLength=0;
 *         int sum=0;//最终和
 *
 *         for(int i=0;i<=nums.length-1;i++){//控制起始位置
 *             sum=0;//易错点:sum 会一直累加，没有被重置为 0
 *             for(int j=i;j<=nums.length-1;j++){//控制终止位置
 *                 sum+=nums[j];
 *                 if(sum>=target){ // 一旦发现子序列和超过了s，更新result
 *                     subLength=j-i+1;// 取子序列的长度
 *                     result=result<subLength?result:subLength;
 *                     break;// 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
 *
 *                 }
 *             }
 *         }
 *         return result==Integer.MAX_VALUE?0:result;
 *
 *
 *     }
 * }
 */

//滑动窗口的思路
//类似于双指针，一个for循环代替两个for循环
//滑动窗口最重要的一个思路就是如何移动起始位置
//for循环中的j指向的是最终位置

public class minimumSizeSubarray {
    public int minSubArrayLen(int target, int[] nums) {
        int begin=0;//起始位置
        int sum=0;//窗口内元素的和
        int result=Integer.MAX_VALUE;//最终返回的结果

        for(int end=0;end<=nums.length-1;end++){
            sum+=nums[end];

            while(sum>=target){
                result=Math.min(result,end-begin+1);
                sum=sum-nums[begin];
                begin++;
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }
}